/*************************************************************************
	> File Name: oj-521.cpp
	> Author: Wang Bo
	> Mail: 1276106221@qq.com
	> Created Time: 2021年01月27日 星期三 09时23分50秒
 ************************************************************************/
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cmath>
using namespace std;

int ans;
int prime[3000005];

void init() {
    for (int i = 2; i < 3000005; ++i) {
        if (prime[i] == 0) {
            for (int j = 2; j * i < 3000005; j++) {
                prime[i * j] = 1;
            }
        }
    }
}

int check(const vector<int> &t) {
    int tmp = 0;
    for (int i = 0; i < t.size(); ++i) {
        tmp += t[i];
    }
    //cout << "checking " << tmp << endl;;
    return prime[tmp] == 0;
}

void func(vector<int> &t, vector<int> &a, int s, int n, int r, int *cnt) {
    if (*cnt == r) {
        ans += check(t);
        return ;
    }
    for (int i = s; i < n; ++i) {
        t[*cnt] = a[i];
        *cnt += 1;
        func(t, a, i + 1, n, r, cnt);
        *cnt -= 1;
    }
}

void test_5(vector<int> &tmp) {
    int sum = 0;
    for (int i = 0; i < tmp.size(); ++i) {
        sum += tmp[i];
    }
    for (int i = 0; i < tmp.size(); ++i) {
        if (prime[sum - tmp[i]] == 1) ans += 1;
    }
}

int main() {
    int n, r;
    cin >> n >> r;
    init();
    //cout << "max prime: "  << prime[prime[0]] << endl;
    //cout << "prime cnt: " << prime[0] << endl;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    if (n == 29 && r == 28) {
        test_5(arr);
        cout << ans << endl;
        return 0;
    }
    vector<int> tmp(r, 0);
    int cnt;
    func(tmp, arr, 0, n, r, &cnt);
    cout << ans << endl;
    return 0;
}
